package BinaryTree;

import java.util.ArrayList;

/*
* 平衡二叉树
* */
public class Offer55isBalanced {
//    ArrayList<Integer> list=new ArrayList<>();
//    public boolean isBalanced(TreeNode root) {
//        dfs(root);
//        for (Integer integer : list) {
//            if(integer>1){
//                return false;
//            }
//        }
//        return true;
//    }
//    int dfs(TreeNode root) {
//        if(root==null){
//            return 0;
//        }
//        int l=dfs(root.left);
//        int r=dfs(root.right);
//        int res=Math.abs(l-r);
//        list.add(res);
//        return Math.max(l,r)+1;
//    }

    /*
    * dfs+剪枝, 遇到不符合条件的节点就直接返回-1;
    * */
    public boolean isBalanced(TreeNode root){
        return recur(root)!=-1;
    }

    int recur(TreeNode root) {
        if(root==null){
            return 0;
        }
        int l=recur(root.left);
        if(l==-1)return -1;
        int r=recur(root.right);
        if(r==-1)return -1;
        return Math.abs(l-r)>1?-1:Math.max(l,r)+1;
    }
}
